这些乱七八糟的方块被数学家称为——沃罗诺伊图，你知道它是怎么计算画出来的吗？其实小学生都能看懂！

「封面」- 带德劳内三角化的 Voronoi

本篇预计阅读时长9min，难度 🌟🌟🌟🌟

大家好，我是科学羊，这里是数学篇第五季第18篇，今天我们谈一个新知识—— Voronoi（沃罗诺伊图）图。

言论

其实大家看封面就知道这是个啥了，是不是感觉很像某个干旱地带的田地呢。当然，这都是自然产生的，至于有没有给人启发，其实不然。但这个图的思想确是给人很重要的依据与应用。

接下来我带大家一起探索下关于沃罗诺伊图的故事。

01 什么是沃罗诺伊图

你可能不知道Voronoi图（也称为Dirichlet镶嵌图或Thiessen多边形），但你一定在生活中无数次见过它们。

无论是在地图学、生物学、计算机科学、统计学，还是在考古学、建筑学和艺术中，Voronoi图都有广泛的应用。这种图形看似简单，却蕴含着令人惊叹的性质。

沃罗诺伊图（Voronoi 图）最早可以追溯到 17 世纪，当时法国数学家笛卡尔（René Descartes） 研究了关于空间划分的问题。到了 19 世纪，Voronoi 图由乌克兰裔俄国数学家 Georgy Voronoi 进行了系统地研究和命名。

最初研究沃罗诺伊图是为了理解和分析空间中点的分布及其相互关系。

通过将空间划分成若干区域，可以研究和解决各种几何、数学以及现实生活中的问题。

那么，到底什么是Voronoi图？

想象一下，你和你的朋友们站在一片空地上。

每个人在地上画一个圆圈，这个圆圈代表你们每个人的地盘。

每个人的地盘是离自己最近的区域。如果两个圈子重叠了，那么在重叠的地方画一条线，把重叠的区域分开。

最后，你们就会得到一幅图，这幅图就是沃罗诺伊图。

那么你们每个人就是沃罗诺伊图的种子点，而每个区域里的点离某个种子点最近就是最近区域。

再比如，想象一下你在一张纸上画n个点，Voronoi图就是将平面细分为n个单元，每个单元包含了平面中最接近一个特定点的区域。

这些单元共同覆盖了整个平面，形成了一个镶嵌结构。

正如上图所示，我们绘制了100个随机点及其对应的Voronoi图。你会看到，每个点都被一个单元格包围，这些单元格的边界在两个或多个点之间完全等距。

换句话说，关键点在于，单元格中的所有区域都比邻近的点更接近单元格中的点。

看到这里你肯定已经想到了很多自然界中相似的场景，比如，从洋葱皮的细胞结构到菠萝蜜的外壳，再到长颈鹿的皮毛，这些图案几乎无处不在！

Voronoi 模式在自然界无处不在｜ (从左上角到右下角: 肌肉的横截面，长颈鹿的皮毛图案，蜻蜓的翅膀，大蒜球，玉米，挂在树上的菠萝蜜。) 资料来源: Nephron，Nirav Shah，KarolinaGrabowska，StarGlade，MaliMaeder，Abi Jacob -meduim

当然，这些图案之所以无处不在，有几个原因。

首先，Voronoi图形成了有效的形状，完全镶嵌了平面，所有空间都被充分利用。如果你想在有限的空间内尽可能多地填充内容，比如肌肉纤维或蜂巢，这是非常方便的。

其次，Voronoi图是一种自发的模式，无论何时，只要有东西从不同的点以均匀的速度增长，就会形成这样的图案。

例如，长颈鹿胚胎中的黑色素分泌细胞分布不均匀，这些细胞负责长颈鹿斑点的深色素沉着。在妊娠过程中，这些细胞释放黑色素，形成向外辐射的斑点。

一个 Voronoi 图是从分散的点不断向外生长得到的 来源: wiki

或许是因为它们自发的“自然”外观，又或是因为它们令人着迷的随机性，Voronoi图被有意地应用在人造结构中。

比如，大家可以查看下图，2008年北京奥运会的水立方就是一个典型案例。

水立方的天花板和外立面采用了Voronoi图的设计，因为它们能让人联想到泡沫的形态，尤其在夜晚，当整个建筑被蓝色灯光照亮时，这种效果更为明显。

当然，Voronoi图的欣赏并不止于现代建筑。

中国宋代的官窑和葛窑陶瓷上独特的裂纹也是一种Voronoi图案。

这些裂纹在冷却过程中故意形成，被称为分层裂解，常产生类似于Voronoi图的斑块模式。这种图案在瓷器中被广泛模仿，成为最受追捧的样式之一。

另外，Voronoi图在图形艺术中也很常见，被用于创造“抽象”模式。

例如，本文的缩略图就是通过生成随机点和构造Voronoi图来创建的，并根据每个单元格的点与方框中随机选择的点的距离进行着色。

图源：Francesco Bellelli

好，既然了解了具体的背景和案例，接下来我们了解下关于Voronoi的数学原理。

02 数学定义及其性质

首先，我们定义一些术语：

1. 种子点：我们用P来表示所有种子点的集合，其中每个种子点用pi表示。例如 P= {p1,p2,...,pn}。

2. 平面上的任意点：我们用x来表示平面上的任意一点。

我们需要计算平面上任意一点 x 到每个种子点 pi 的距离。通常我们用欧几里得距离来计算，公式是：

两点之间的距离公式

用公式表示就是：

这里，x=(x1,x2) 和 pi=(pi1,pi2)

虽然数学定义听起来复杂，但我们可以用简单的例子来理解。

假设我们有三个种子点p1,
p_2p2, 和
p_3p3，它们的坐标分别是(1,2),(4,6), 和(7, 3)(7,3)。

假如我们想知道一个点x=(5,4) 属于哪个沃罗诺伊单元，该怎么计算呢？

好，接下来我们先计算距离：

综上所述就会发现，d(x,p2)和d(x,p3)都是根号5，均比d(x,p1)等于根号20要小，所以点x=(5,4)属于p2和p3的分界线上！

好，这时候我们再看看关于沃罗诺伊单元定义就懂了：

二十个点和沃罗诺伊单元格

03 Voronoi图的其他算法及应用

如果你是机器学习领域的开发人员，应该会很熟悉K近邻算法。

很简单，其实k-NN 算法是一种基于距离的分类和回归算法。

给定一个待分类点，k-NN 算法会找到离该点最近的 k 个点，然后根据这些点的标签或数值来决定待分类点的类别或数值。

k-NN算法用于分类、回归和聚类问题，通过训练数据集中的k个最接近的例子进行值预测。

由于Voronoi图将空间划分为包含与每个种子点最近的多边形，Voronoi单元的边界完全对应于1-最近邻问题的决策边界。

所以机器学习也不难，它里面的很多算法也是基于很多前置数学基础。

另外，还有一种建模方式——德劳内三角化。

德劳内三角化是Voronoi图的对偶图，通过连接每个点与相邻单元中的点，可以得到德劳内三角化的图。

如下图：这种三角化具有使三角形的最小角度最大化的特性，避免了非常锐角的三角形，非常适合用于建模曲面和物体。

带德劳内三角化的Voronoi图

劳埃德松弛算法是一种与Voronoi图相关的实用算法，通过交替构建Voronoi图和寻找每个细胞的质心，不断迭代生成更均匀的Voronoi单元。

经过多次迭代，单元格会趋向于更圆的形状，点的分布更加均匀，最终形成质心Voronoi图。

Delaunay 三角形的构造使得任何一个点都不会落在围绕每个三角形的圆圈内。来源: Wiki

劳埃德算法在数据科学中作为K平均算法的基础，被广泛应用于聚类分析。此外，它还用于生成平滑的网格、图像抖动以及程序化地图生成。

如何构造Voronoi图？

可以通过逐个构建每个细胞来构造Voronoi图，方法是延伸连接每个点组合的片段的平分线。

然而，这种技术效率低下，因此提出了更有效的替代方案。

例如，扫线算法通过二叉查找树和优先级队列操作逐步构建Voronoi单元，德劳内三角化技术也可以用于构建Voronoi图。

结语

Voronoi图不仅是一种数学工具，更是一种自然与艺术的表达形式。

它们在自然界中广泛存在，从微观细胞到宏观建筑，无处不在的Voronoi图展示了自然界和人类智慧的奇妙联系。

好，今天就先这样啦～

好，今天先这样啦～

科学羊🐏  2024/07/09

祝幸福~

参考文献：

[1].https://towardsdatascience.com/the-fascinating-world-of-voronoi-diagrams-da8fc700fa1b

「感恩关注，科学羊持续为您带来最好的科普知识」

往期推荐